/*
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.
*/

/* O(N) solution */
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        height.push_back(0);
        int maxarea = 0;
        for (int i = 0; i < height.size(); ) {
            if (s.empty() || height[i] > height[s.top()]) {
                s.push(i++);
            } else {
                // compute area
                int idx = s.top(); s.pop();
                maxarea = max(maxarea, height[idx]*(s.empty()?i:(i-1-s.top())));
            }
        }
        return maxarea;
    }
};

#if 0
/* O(N^2) worst case solution */
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int minv, maxarea = 0;
        for (int i = 0; i < height.size(); i++) {
            if (i < height.size()-1 && height[i] <= height[i+1]) continue;
            minv = height[i];
            for (int j = i; j >= 0; j--) {
                minv = min(minv, height[j]);
                int area = (i-j+1)*minv;
                if (area > maxarea) maxarea = area;
            }
        }
        return maxarea;
    }
};
#endif
